package com.kaifamiao.arrays;

// 二分查找(非递归实现)
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = { 1, 3, 4, 7, 8, 9 };

        // 指定被查找的值
        final int key = 9;
        // 用于记录 key 再 arr 中位置的变量
        int index = -1;

        // 确定起点 (原始的起点是数组开头)
        int begin = 0;
        // 确定终点 (原始的终点是数组末尾)
        int end = arr.length - 1;

        while( begin <= end ) {
            // 计算处于begin和end中间位置的元素的索引
            int middle = begin + ( (end - begin) >> 1 );
            // System.out.printf( "begin: %d, middle: %d, end: %d\n", begin , middle , end);
            // 若 key 大于 middle 处的元素
            if (key > arr[middle]) {
                // 则以 middle 为新的起点
                begin = middle + 1 ;
            } else if (key == arr[middle]) {
                // 若 key 与 arr[middle] 相等则记录该索引
                index = middle;
                break;
            } else {
                // 以 middle 为新的终点
                end = middle - 1 ;
            }
        }
        System.out.println( index );
    }
}
